package sit.engreal.leetcode.problems100;

import org.junit.jupiter.api.Assertions;

import java.util.Arrays;

/**
 * <a href="https://leetcode.cn/problems/3sum-closest/">16. 最接近的三数之和</a>
 */
public class LeetCode16 {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int minGap = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int left = i + 1;
            int right = nums.length - 1;
            while (left < right) {
                final int sum = nums[i] + nums[left] + nums[right];
                if (Math.abs(minGap) > Math.abs(sum - target)) {
                    minGap = sum - target;
                }
                if (sum < target) {
                    left++;
                } else if (sum > target) {
                    right--;
                } else {
                    return target;
                }
            }
        }
        return target + minGap;
    }

    public static void main(String[] args) {
        final LeetCode16 demo = new LeetCode16();
        Assertions.assertEquals(2,
                demo.threeSumClosest(new int[]{-1, 2, 1, -4}, 1));
        Assertions.assertEquals(0,
                demo.threeSumClosest(new int[]{0, 0, 0}, 0));
    }
}
